package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串 s，找到 s 中最长的回文子串。
 * @version 1.0
 * @date 2021/11/13 8:44
 * @see countSubstrings
 */
public class longestPalindrome {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccb"));

    }

    // 中心扩撒法，回文串的中心位置可能在 第i 元素上（奇数回文串），也可能在 第i个元素 和第 i+1 个元素的中间（偶数回文串）
    static String longestPalindrome(String s) {

        if (s.length() <= 1) {
            return s;
        }
        // 因为截取字符串消耗性能，所以先记录回文串的 起始位置 和 回文长度，最后做一次截取
        int beginIndex = 0;
        int maxLength = 0;
        for (int i = 0; i < s.toCharArray().length - 1; i++) {
            // 偶数回文
            int evenMaxLength = isPalindrome(i, i + 1, s);
            // 奇数回文
            int oddMaxLength = isPalindrome(i, i, s);
            if (Math.max(evenMaxLength, oddMaxLength) > maxLength) {
                maxLength = Math.max(evenMaxLength, oddMaxLength);
                beginIndex = i - (maxLength - 1) / 2;
            }
        }
        return s.substring(beginIndex, beginIndex + maxLength);
    }

    static int isPalindrome(int left, int right, String s) {
        while (left >= 0 && right < s.length())
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        return right - left - 1;
    }

    // Manacher‘s Algorithm
}


